package com.kevinkk.tree;

import java.util.*;

/**
 * 给你一个【含重复值】的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 */

public class FindModeInBinarySearchTree {
    class Solution {
        // 需要定义一个全局的 count， 否则递归的时候无法将 count 信息带出来
        int maxCount = Integer.MIN_VALUE, count = 0;
        List<Integer> res = new ArrayList<>();
        TreeNode pre = null;

        public int[] findMode(TreeNode root) {
            traversal(root);
            int[] arr = new int[res.size()];
            for(int i = 0; i < res.size(); i++) arr[i] = res.get(i);
            return arr;
        }

        private void traversal(TreeNode root){
            if(root == null) return;
            traversal(root.left);
            if(pre != null && pre.val == root.val){
                count ++;
            }else{
                count = 1;
            }
            if(count == maxCount){
                res.add(root.val);
            }else if(count > maxCount){
                res.clear();
                res.add(root.val);
                maxCount = count;
            }
            pre = root;
            traversal(root.right);
        }
    }
}
